package com.cy.algorithm.lru;

/**
 * head->1->2->3->4
 *
 * @author yuchen
 */
public class MyLinkedList<T> {

    Node<T> head;
    int size;

    /**
     * 新增功能
     * 头部添加
     *
     * @param data 要添加的数据
     */
    public void put(T data) {
        Node<T> tempHead = head;
        head = new Node<>(data, tempHead);
        size++;
    }

    /**
     * 指定位置添加
     *
     * @param index 索引值
     * @param data  添加的数据
     */
    public void put(int index, T data) {
        checkIndex(index);
        Node<T> pre = new Node<>(null, head);
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            if (curr.next != null) {
                pre = curr;
                curr = curr.next;
            }
        }
        pre.next = new Node<>(data, curr);
        size++;
    }

    public void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException(String.format("index=%s,size=%s", index, size));
        }
    }

    /**
     * 移除尾部节点
     *
     * @return 返回当前节点的数据
     */
    public T removeLast() {
        if (size == 0) {
            return null;
        }
        Node<T> pre = new Node<>(null, head);
        Node<T> curr = head;
        while (curr.next != null) {
            pre = curr;
            curr = curr.next;
        }
        pre.next = null;
        size--;
        return curr.data;
    }

    public T remove(int index) {
        checkIndex(index);
        Node<T> pre = new Node<>(null, head);
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            pre = curr;
            curr = curr.next;
        }
        pre.next = curr.next;
        T data = curr.data;
        //GC
        curr = null;
        size--;
        return data;
    }

    public void set(int index, T data) {
        checkIndex(index);
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        curr.data = data;
    }

    public Node<T> get(int index) {
        checkIndex(index);
        Node<T> curr = head;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr;
    }

    public T get() {
        if (head == null) {
            return null;
        }
        return head.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<T> temp = head;
        while (temp != null) {
            sb.append(temp.data).append(" ");
            temp = temp.next;
        }
        return "size=" + size + ":" + sb.toString();
    }


    public static void main(String[] args) {
        MyLinkedList<Integer> linkedList = new MyLinkedList<>();
        for (int i = 0; i < 10; i++) {
            linkedList.put(i);
        }
        System.out.println(linkedList.toString());
        linkedList.put(3, 9);
        System.out.println(linkedList.toString());
        linkedList.removeLast();
        System.out.println(linkedList.toString());
        linkedList.remove(2);
        System.out.println(linkedList.toString());
        linkedList.removeLast();
        System.out.println(linkedList.toString());
        linkedList.removeLast();
        System.out.println(linkedList.toString());
    }

    static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }
}
